In digital data communications systems, it is common for data packets transmitted over a communications channel to be corrupted by errors, e.g., when communicating in hostile environments. Wireless radio communications are often conducted in an especially hostile environment. The radio channel is subjected to a barrage of corrupting factors including noise, rapidly changing communications channel characteristics, multi-path fading, and time dispersion which may cause intersymbol interference, and interference from adjacent channel communications.
There are numerous techniques that may be employed by a receiver to detect such errors. One example of an error detection technique is the well-known cyclic redundancy check (CRC). Other techniques used in packet data communications employ more advanced types of block codes or convolutional codes to accomplish both error detection and error correction. For both error detection and error correction, channel coding is applied which adds redundancy to the data. When the information is received over the communications channel, the received data is decoded using the redundancy to detect if the data has been corrupted by errors. The more redundancy built into a unit of data, the more likely errors can be accurately detected, and in some instances, corrected using a forward error correcting (FEC) scheme. In a pure FEC scheme, the flow of information is uni-directional, and the receiver does not send information back to the transmitter if a packet decoding error occurs.
In many communications systems, including wireless communications, it is desirable (if possible) to have a reliable data delivery service. Most reliable data delivery protocols use a fundamental retransmission technique where the receiver of the data responds to the sender of the data with acknowledgments (ACKs) and/or negative acknowledgments (NACKs). This technique is commonly known as Automatic Repeat reQuest (ARC) transaction processing. Coded data packets are transmitted from a sender to a receiver over a communications channel. Using the error detection bits (the redundancy) included in the coded data packet, each received data packet is processed by the receiver to determine if the data packet was received correctly or corrupted by errors. If the packet was correctly received, the receiver transmits an acknowledgment (ACK) signal back to the sender. If the receiver detects errors in the packet, it may also send an explicit negative acknowledgment (NACK) to the sender. When the NACK is received, the sender can retransmit the packet. In a pure ARQ system, the channel code is only used for error detection.
In hybrid ARQ (HARQ), features of a pure FEC scheme and a pure ARQ scheme are combined. Error correction and error detection functions are performed along with ACK/NACK feedback signaling. The channel code in a hybrid ARQ scheme may be used for both error correction and error detection. Alternatively, two separate codes can be used: one for error correction and one for error detection. A NACK signal is sent back to the transmitter if an error is detected after error correction. The erroneously received data packet in this first type of hybrid ARQ system is discarded. A more efficient hybrid ARQ scheme is to save the erroneously received and negatively acknowledged data packet and then combine it in some way with the retransmission. Hybrid ARQ schemes that use packet combining are referred to as hybrid ARQ with combining. In a hybrid ARQ combining scheme, the “retransmission” may be an identical copy of the original packet. If the retransmission is identical to the original transmission, the individual symbols from multiple packets are combined to form a new packet consisting of more reliable symbols. Alternatively, the retransmission may use incremental redundancy (IR). In IR packet combining, additional parity bits are transmitted which makes the error correction code more powerful than, and generally superior to, identical packet combining.
Equally as important as reliable data delivery is fast data delivery. To deliver data quickly, many data communications systems strive to increase the available peak transmission rate and to reduce delay. Reducing delay is particularly important in order to support high data rates efficiently.
One example area where speed is important is in High Speed Downlink Packet Access (HSDPA) channels to employed in some mobile radio communications networks. Currently, it is proposed the HSDPA channels employ a HARQ protocol as specified in the 3GPP Technical Specification (TS) 25.308 v0.1.0 “UTRA High Speed Downlink Packet Access,” released by the 3GPP (3rd Generation Partnership Project) in September 2001. The specified HARQ protocol retransmission scheme is implemented using retransmission entities in an extension of the media access control (MAC) protocol layer in a base station (sometimes referred to as a “Node B”) and a mobile user equipment (UE). The retransmission entity stores erroneously received data blocks, for example in the UE, and combines them with corresponding, later-received retransmissions of the same data blocks. Two (or more) erroneously received copies of a data block may be combined in the UE receiver into a correct data block. The MAC-HSDPA retransmission entity delivers correctly received data blocks to a higher radio link control (RLC) protocol layer as RLC packet data units (PDUs).
The HARQ protocol defined in that specification includes a reordering entity that achieves in-sequence delivery of received data units to the higher RLC protocol layer. This function is necessary because transmitted data units numbered 0, 1, 2, 3, . . . experience varying transmission delays caused by the air-interface, and mainly as a result of a different number of retransmissions needed for each data unit. Thus, if data unit 2 is correctly received before data unit 1, data unit 2 is buffered until data unit 1 is correctly received before both data units 1 and 2 are provided to the upper protocol layer.
Unfortunately, the specified HARQ protocol and ARQ protocols in general will “stall” in certain situations. In the simple example just given, a stall situation would occur when the reordering entity waits for a long time (or it may even wait indefinitely) for data-unit 1 to be correctly received. This may occur when a NACK message for data block has been corrupted or is otherwise erroneously identified when received as an ACK. As a result of this error, there will be no retransmission of the data unit, even though it should be retransmitted. Another stall situation occurs when the retransmission of a data unit is interrupted because the number of retransmissions exceeds a limit or because other higher priority data must be sent. The retransmission may be cancelled or resumed at a later time. In general, a stall occurs when a data unit is lost or will not be satisfactorily received in a foreseeable, reasonably short time.
It is an object of the present invention to avoid stall situations in order to decrease data delays, and ultimately, increase data throughput rates.
It is an object of the present invention to provide a method and an apparatus for stall avoidance for an ARQ protocol that is relatively easy to implement.
In addition to stall problems, ARQ protocols also suffer from sequence number ambiguities if the data unit numbering scheme repeats in modulo fashion, e.g., modulo-8 sequence numbering follows this kind of repeating pattern: 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2 . . . . Assume for example that a data unit with sequence number (SN) 6 is sent at a first time interval as part of a first set of data units numbered 0–7, but the SN 6 data unit is not satisfactorily received at the receiver. A request for retransmission of data unit SN 6 is sent back to the transmitter. However, before the transmitter retransmits data unit SN 6 from the first set, the transmitter transmits another data unit SN 6 from a second set of data units numbered 0–7 for the first time. The receiver detects the just-transmitted-for-the-first-time data unit SN 6, rather than the retransmitted data unit SN 6 as requested The receiver cannot detect or resolve this ambiguity, which results in errors.
It is an object of the present invention to provide a mechanism that avoids such ambiguities either at the transmitter, the receiver, or at both.
The present invention provides a stall avoidance mechanism that may be used alone or in conjunction with an ambiguity avoidance mechanism. Both decrease data delays and increase data throughput rates.
Stall avoidance is accomplished by determining whether a stall condition exists with respect to receiving a missing data unit. The term “missing data unit” includes a data unit that has not been received, a data unit that is incorrectly received, or an incorrectly received data unit that cannot be corrected. Alternatively, a missing data unit may be viewed as a data unit that the receiver requests the transmitter to retransmit for any reason.
In one non-limiting, example embodiment, a timer is started if a data unit is received having a sequence number greater than the sequence number of the missing data unit. If the timer expires before the missing data unit is received, thereby indicating that a stall condition exists, received data units having sequence numbers less than the sequence number of the missing data unit are removed from the receiver buffer and provided to the higher protocol layer for further processing. On the other hand, if the missing data unit is received before the timer expires, the timer is stopped and the received data units having sequence numbers less than that of the missing data unit are removed from the buffer and sent to the higher protocol layer.
In ARQ transmission schemes where data units are transmitted in sequence modulo-N, N being a larger sequence number, retransmission ambiguities may be avoided using a retransmisson window in the transmitter and/or a receive window in the receiver. The size of the retransmission window preferably corresponds to a number of data units less than N, e.g., N/2. The retransmission window is positioned with respect to a retransmit buffer to avoid ambiguity in the receiver when receiving data units with sequence numbers of originally-transmitted data units and retransmitted data units. More specifically, retransmission of a data unit is only permitted when its sequence number is within a current position of the transmission window in the sequence numbering. An upper end of the window is positioned in the retransmit buffer at a sequence number that is less than or equal to a difference between the highest sequence number most recently transmitted and the window size. The transmission window is moved to a next sequence number position in the modulo-N sequence after each data unit is transmitted.
The receiver may also use a receiving window as another way to avoid ambiguity between orignally-transmitted and retransmitted data units. The size of the receiving window preferably corresponds to a number of data units less than N, e.g., N/2. An upper end of the receiving window is positioned at a data unit sequence number less than or equal to a difference between a highest sequence number most recently received and the window size. A received data unit having a received sequence number within a current position of the receiving window is stored at a location in the buffer corresponding to its sequence number. However, if a received data unit inside the window was previously received, it is discarded. If it is outside the receiving window, the data unit is also stored in the buffer at its corresponding sequence number position, and the receiver window is advanced so that the sequence number of that data unit forms the upper end of the window. After moving the receive window, data units having a sequence number less than that the lower end of the window are removed from the buffer.
Although each mechanism may be used independently of the other, a preferred example embodiment uses a stall avoidance timer, a retransmission window in the transmitter, and a receive window in the receiver.